What is Page Fault?

A page fault happens when the required page is not found in memory. The system then brings that page from disk into RAM.

Page Replacement Algorithms in Operating System

Page Replacement Algorithms are used in virtual memory systems to decide which page should be removed from main memory when a new page needs to be loaded and memory is full.

Why Page Replacement is Needed

• Main memory has limited space
• Programs may be larger than available RAM
• Efficient memory usage is required
• To reduce page faults

Types of Page Replacement Algorithms

1. FIFO (First In First Out)

FIFO (First In First Out) Page Replacement Algorithm is one of the simplest memory management techniques used by an operating system to handle page faults. In this algorithm, the page that enters the memory first is removed first when new space is required.

FIFO Page Replacement Algorithm – Solved Example

Problem Statement

• Page Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 1, 2, 0
• Number of Page Frames: 3
• Algorithm Used: FIFO

What is FIFO Page Replacement?

FIFO stands for First In First Out. According to this method, the oldest page present in main memory is replaced whenever a new page arrives and no free frame is available. The algorithm does not consider how frequently or recently a page is used.

Step-by-Step Explanation

Initially, all page frames are empty. When pages are accessed one by one, a page fault occurs whenever the required page is not present in memory. If memory is full, FIFO removes the page that was loaded earliest.

• Pages 7, 0, and 1 cause page faults and fill the three frames.
• When page 2 arrives, page 7 (oldest) is replaced.
• Whenever a page already exists in memory, it results in a page hit.
• This process continues until the full reference string is executed.

Final Results

• Total Page Faults: 12
• Total Page Hits: 3
• Number of Frames: 3

Page Fault Rate

Page Fault Rate = Number of Page Faults / Number of Frames
= 12 / 3 = 4.0

Key Observations

• FIFO replaces pages based only on arrival time.
• It does not consider future or recent usage.
• This algorithm may suffer from Belady’s Anomaly.
• Despite limitations, FIFO is widely used for learning purposes.

Exam-Oriented Short Note

FIFO page replacement algorithm removes the oldest page from memory when a new page arrives and memory is full. In the given example with three frames, FIFO produces 12 page faults and 3 page hits.

2. LRU (Least Recently Used)

LRU removes the page that has not been used for the longest time. It is based on recent usage patterns.

Example: Page Fault Calculation using LRU Page Replacement Algorithm

In this example, we are given a page reference string and a fixed number of page frames. The task is to calculate the total number of page faults using the Least Recently Used (LRU) Page Replacement Algorithm. LRU replaces the page that has not been used for the longest period of time.

Given Data

• Page Reference String: 7, 0, 1, 2, 0, 2, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
• Number of Frames: 4
• Replacement Policy: LRU (Least Recently Used)

Step-by-Step Explanation

Initially, all memory frames are empty. As pages are referenced one by one, they are loaded into the available frames. Whenever a referenced page is not found in memory, a page fault occurs.

Once all four frames become full and a new page needs to be loaded, the LRU algorithm checks which page was used least recently and replaces that page with the new one. This decision is based entirely on past usage history.

For example, when page 4 is referenced and all frames are already occupied, the algorithm removes the page that was accessed farthest in the past. This process continues for every page reference until the entire reference string is processed.

Final Observation

• Total Page Faults: 8
• Total Page Hits: 12
• Total Page References: 20

Performance Calculation

The page fault rate is calculated by dividing the number of page faults by the total number of page references.

• Page Fault Rate: (8 / 20) × 100 = 40%
• Hit Rate: (12 / 20) × 100 = 60%

Conclusion

This example clearly shows how the LRU page replacement algorithm works by tracking recent page usage. LRU generally performs better than FIFO because it considers actual usage behavior, reducing unnecessary page replacements.

3. Optimal Page Replacement

Optimal algorithm removes the page that will not be used for the longest time in the future. It gives minimum page faults but is not practical in real systems.

Example: Page Fault Calculation using Optimal Page Replacement Algorithm

In this example, we calculate the number of page faults using the Optimal Page Replacement Algorithm. This algorithm replaces the page that will not be used for the longest period of time in the future. Because it has complete knowledge of future page references, it provides the minimum possible number of page faults.

Given Information

• Page Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 1, 2, 0
• Number of Frames: 4
• Algorithm Used: Optimal Page Replacement

Step-by-Step Explanation

Initially, all four frames are empty. As pages are requested one by one, they are loaded into the available frames. Every time a page is not found in memory, a page fault occurs.

Once the frames are full and a new page needs to be loaded, the Optimal algorithm checks all pages currently in memory and looks ahead in the reference string to determine which page will be used farthest in the future. That page is selected for replacement.

For example, when page 4 is referenced and memory is already full, the algorithm compares the future usage of existing pages and removes the page that will not be needed for the longest time. This decision minimizes future page faults.

This process continues for each page reference until the entire reference string is processed.

Final Results

• Total Page Faults: 7
• Total Page Hits: 8

Performance Calculation

The page fault rate gives an idea of how frequently page faults occur during execution.

• Page Fault Rate: (7 / 15) × 100 ≈ 46.7%
• Hit Rate: (8 / 15) × 100 ≈ 53.3%

Conclusion

This example demonstrates why the Optimal Page Replacement Algorithm produces the lowest possible number of page faults. However, it is mainly used for theoretical analysis because predicting future page references is not practical in real operating systems.

4. MRU (Most Recently Used)

MRU removes the most recently used page. It works well only in specific access patterns.

Example: Page Fault Calculation using Page Replacement Algorithm

In this example, we are given a page reference string and a fixed number of memory frames. Our objective is to calculate the total number of page faults, page fault rate, and page fault ratio during execution.

Given Data

• Page Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
• Number of Frames: 4

Explanation

Initially, all memory frames are empty. When the first few pages are accessed, they are placed into the available frames. Since the pages are not already present in memory, each of these accesses causes a page fault.

Once all four frames are filled, every new page request is checked against the pages currently stored in memory. If the requested page is already available, it is counted as a page hit. If it is not present, a page fault occurs and one of the existing pages is replaced according to the page replacement rule used in the example.

This process continues for each page reference in the sequence. Every miss is counted as a page fault, and every successful access is counted as a hit.

Final Observation

• Total Page Faults (Misses): 12
• Total Page Hits: 8

Performance Calculation

The rate and ratio of page faults help us understand how efficiently memory is being used.

• Rate of Page Fault: Page Faults / Number of Frames = 12 / 4 = 3
• Page Fault Ratio: (Page Faults / Total Page Requests) × 100 = (12 / 20) × 100 = 60%
• Hit Ratio: 100% − Page Fault Ratio = 40%

Conclusion

This example clearly shows how page faults occur when the required page is not present in memory. By analyzing page faults and hit ratios, we can evaluate the effectiveness of a page replacement strategy and understand how memory performance impacts overall system efficiency.

Comparison of Page Replacement Algorithms

Algorithm	Replacement Basis	Performance	Complexity
FIFO	Arrival Time	Low	Simple
LRU	Recent Usage	High	Complex
Optimal	Future Use	Best	Theoretical
MRU	Recent Access	Limited	Simple

Advantages

• Efficient Use of Memory: The system loads only the required pages into main memory, which helps in utilizing RAM effectively and avoids unnecessary memory occupation.
• Faster Program Start: Programs can begin execution without waiting for the entire process to be loaded into memory, resulting in quicker startup times.
• Reduced Memory Wastage: Since unused parts of a program are not loaded, memory wastage is minimized, allowing more processes to reside in memory simultaneously.
• Support for Large Applications: Applications larger than physical RAM can run smoothly because secondary storage is used as an extension of main memory.
• Improved Multitasking: Multiple programs can execute at the same time as memory is allocated dynamically based on actual demand.

Disadvantages

• Performance Degradation due to Page Faults: Frequent page faults cause the system to access secondary storage, which is much slower than RAM, leading to reduced system performance.
• Additional Overhead: Managing page tables, handling page faults, and maintaining memory mappings introduce extra overhead for the operating system.
• Thrashing Problem: If too many page faults occur, the system may spend more time swapping pages than executing processes, severely affecting performance.
• Complex Implementation: Demand-based memory management requires sophisticated algorithms, making the operating system more complex to design and maintain.

Summary

• Virtual memory uses disk as extra memory
• Demand paging loads pages only when needed
• Page fault occurs when page is missing
• Improves performance and memory usage